package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC55 {

    public boolean canJump(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }

        int rightMax = 0;
        for (int i = 0; i < nums.length; i++) {
            if (rightMax < i) {//which indicates this pos i cannot be arrive
                break;
            }
            rightMax = Math.max(rightMax, nums[i] + i);
        }

        return rightMax >= nums.length - 1;
//        return canJumpRecur(nums, nums.length - 1);
    }

    public boolean canJumpRecur(int[] nums, int destPos) {
        if (destPos < 0 || nums.length < 0) {
            return false;
        }

        int fromPos = destPos - 1;
        while (fromPos > 0) {
            if (nums[fromPos] + fromPos < destPos) {
                --fromPos;
                continue;
            }

            if (canJumpRecur(nums, fromPos)) {
                return true;
            }

            --fromPos;
        }

        return nums[fromPos] + fromPos >= destPos;
    }


    public static void main(String[] args) {
        LC55 an = new LC55();
        int[] arr = {2, 0, 6, 9, 8, 4, 5, 0, 8, 9, 1, 2, 9, 6, 8, 8, 0, 6, 3, 1, 2, 2, 1};

        System.out.println(an.canJump(arr));
    }
}
